Section: New Results

Genome Structure

Participants : Jacques Nicolas [contact] , Dominique Lavenier, François Coste, Catherine Belleannée, Olivier Sallou, Fabrice Legeai, Guillaume Rizk, Guillaume Chapuis, Matthias Gallé, Anthony Bretaudeau.

• GPU accelerated RNA folding algorithm The main kernel of the widely used RNA folding package Unafold has been accelerated using GPU boards by reordering computations to enable tiled computations and good data reuse [37] , [2] .

• GPU accelerated QTL algorithm Our GPU/multicore implementation performs up to 20 times faster than the previous multicore implementation and allows extensive QTL analysis to be conducted in a reasonable time, while maintaining the same level of precision [35] .

• Hierarchical structure of genomes. In [7] , we proposed to split the classical smallest grammar problem into two tasks: (1) choosing the constituents of the grammar and (2) finding the smallest grammar parsing given these constituents. This defines properly the search space for this problem and, as we have shown how to solve in polynomial time the second task, this opens doors for new algorithms finding smaller grammars as shown on a generic compression benchmark (up to 10%). In [6] , we have worked on the scalability to propose a new algorithm able to handle whole genomes: on this kind of sequences, the size reduction is still about 10% for a comparable execution time with respect to state-of-the art algorithms.

• Data compression By using grammars with rigid patterns as words, we were able to achieve a compression rate up to 25% better compared to the previous best DNA grammar-based coder, and just below state-of-the-art dedicated DNA compressors [1] .

• CRISPR Modeling and identification: CRISPR (Clustered regularly interspaced short palindromic repeats) are small repeats present in a number of bacterial and archaeal species. We proposed the most complete database on these elements (http://crispi.genouest.org ), elaborating for the first time a complete study of the palindromic nature of these repeats. The analysis has made an extensive use of our Logol Parser to decipher stem-loop structures [40] .

• Aphid genetics We participated in a genetic study aiming at comparing the rates of evolution of genes enclosed in aphid sexual chromosome (X) to autosomal genes. In order to do so, we provided particular microsatellites for the selection of genomic sequences, as well as tools for studying their genomic environment. [13] [Online publication: http://mbe.oxfordjournals.org/content/early/2011/10/12/molbev.msr252]